Enumerative coding provides a mapping from a fixed length message to a codeword comprising a sequence of symbols. Further, the mapping of enumerative coding may generate codewords in which the symbol sequences satisfy one or more predetermined constraints. For example, the predetermined constraint for an exemplary binary codeword may stipulate that there is at least a zero (0) between any two ones (1). The ability of enumerative coding to generate codewords that satisfy a predetermined constraint has broad implications for a variety of fields including, but not limited to, data storage and transmission. Enumerative coding was first described by Thomas M. Cover, “Enumerative Source Coding,” IEEE Transactions on Information Theory, Vol. IT-19, No. 1, January 1973, pp. 73-77.
In general, the codewords produced by enumerative coding may be considered either one dimensional (1-D) codewords or two dimensional (2-D) codewords (or 2-D codeword arrays). For example, the codeword may be represented by a string of symbols as a 1-D codeword (e.g., 110010010). Alternatively, the codeword may be represented as a 2-D array of symbols referred to as a codeword array. For example, the 2-D codeword array may be represented as a rectangular array having m rows and n columns. As with codewords, the constraints may also be 1-D constraints or 2-D constraints, especially when considering 2-D codeword arrays. For example, a 2-D constraint may constrain symbol sequences in both the rows and the columns of the 2-D codeword array.
In general, enumerative coding may be readily implemented in an exact form for 1-D codewords with 1-D constraints. Unfortunately 2-D codeword arrays that satisfy 2-D constraints pose a significant challenge for enumerative coding, especially as a size of the 2-D codeword arrays is increased. As such, for enumerative coding that involves relatively large 2-D codeword arrays, approximate enumerative coding has been introduced (see for example, Ordentlich et al., “Capacity Lower Bounds and Approximate Enumerative Coding for 2-D Constraints,” IEEE Intl. Symp. On Information Theory, Jun. 24-29, 2007, pp. 1681-1685).
Certain embodiments of the present invention have other features that are one of in addition to and in lieu of the features illustrated in the above-referenced figures. These and other features of the invention are detailed below with reference to the preceding drawings.